#include <vector>
#include <iostream>
#include "common.h"
#include "entry.h"

namespace VirtualR {

std::vector<Entry_t> compact(std::vector<std::vector<Entry_t>> inputs) {
  uint32_t size = inputs.size();
  std::vector<Entry_t> res;
  auto it = inputs.begin();
  for (int32_t i = 0; i < size; i++) {
    res = do_merge(res, inputs[i]);
  }
  return res;
}

std::vector<Entry_t> do_merge(std::vector<Entry_t> input1, std::vector<Entry_t> input2) {
  std::vector<Entry_t> res;
  if (input1.size() == 0) {
    res = input2;
    return res;
  }
  if (input2.size() == 0) {
    res = input1;
    return res;
  }
  auto it1 = input1.begin();
  auto it2 = input2.begin();
  while (it1 != input1.end() && it2 != input2.end()) {
    if (it1->key < it2->key) {
        res.emplace_back(it1->key, it1->value);
        it1++;
    } else {
        res.emplace_back(it2->key, it2->value);
        it2++;
    }
  }
  while (it1 != input1.end()) {
    res.emplace_back(it1->key, it1->value);
    it1++;
  }

  while (it2 != input2.end()) {
    res.emplace_back(it2->key, it2->value);
    it2++;
  }
  return res;
}
}